package com.example.zxd;

import java.util.Scanner;

/**
 * 进制转换 <p>
 * 描述：将一个十进制数N转换成R进制数输出，2 ≤ R ≤ 16，R ≠ 10。<p>
 * 输入：多行。第一行指出以下一共有多少组数据，后续每行包含两个整数N和R，以空格分隔，-100000 ≤ N ≤ 100000，
 * 2 ≤ R ≤ 16，R ≠ 10。<p>
 * 输出：多行。每行给出转换后的R进制数。<p>
 * 样例输入：<p>
 * 3<p>
 * 7 2<p>
 * 23 12<p>
 * -4 3<p>
 * 样例输出：<p>
 * 111<p>
 * 1B<p>
 * -11
 *
 * @author: scarborough
 * @datetime: 2025/3/19 - 15:04
 * @status: AC
 */
public class PROB1004 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int groups = sc.nextInt();
        for (int i = 0; i < groups; i++) {
            int n = sc.nextInt(); // 十进制数 N
            int r = sc.nextInt(); // 要转换的进制 R
            if (n == 0) { // 不能忘记 n = 0 的情况
                System.out.println(0);
            } else if (n < 0) { // 不能忘记 n < 0 的情况
                n = -n;
                String res = convert(n, r);
                System.out.println("-" + res);
            } else {
                System.out.println(convert(n, r));
            }
        }
    }

    /**
     * 进制转换实际方法
     *
     * @param n 十进制数 N
     * @param r 要转换的进制 R
     * @return 转换后的数字（可能大于十进制，用字符串表示）
     */
    private static String convert(int n, int r) {
        StringBuilder sb = new StringBuilder();
        if (r < 10) {
            while (n > 0) {
                int temp = n % r;
                sb.append(temp);
                n /= r;
            }
        } else {
            while (n > 0) {
                int temp = n % r;
                if (temp >= 10) {
                    char c = (char) (temp - 10 + 'A');
                    sb.append(c);
                } else {
                    sb.append(temp);
                }
                n /= r;
            }
        }
        return sb.reverse().toString();
    }
}
